#include <stdio.h>
#include <stdlib.h>

//调试
//gcc -g hello.c
//gdb a.out

typedef int data_t;

typedef struct linknode {
    data_t data;
    struct linknode *next;
} link_t;

link_t *create_link()
{
    //申请空间 并初始化
    link_t *head;
    head = malloc(sizeof(link_t));
    head->data = 20;
    head->next = NULL;
    return head;
}

int ins_head_link(link_t *head, const data_t *data)
{
    //1. 申请节点空间
    //2. 保存后一个元素的节点地址
    //3.头节点保存新创建节点地址
    if(NULL == head || NULL == data) return -2;

    link_t *newnode;
    newnode = malloc(sizeof(link_t));
    newnode->data = *data;
    newnode->next = head->next;
    head->next = newnode;
    return 0;
}

int ins_index_link(link_t *head, int index, int data)
{

    int i;
    link_t *newnode, *node, *parent, *nnode;

    //1. 创建一个新的节点
    newnode = malloc(sizeof(link_t));
    newnode->data = data;
    newnode->next = NULL;

    //2. 查找指定序号的节点
    parent = head;
    node = parent->next;
    i = 0;
    while(NULL != node->next) {
        if(i == index) {
            //序号匹配，更改前后节点的指向
            parent->next = newnode;
            newnode->next = node;
        }
        parent = node;
        node = node->next;
        i++;
    }
    return 0;
}

int del_head_link(link_t *head) {
    link_t *tmp;
    tmp = head->next;
    head->next = tmp->next;
    free(tmp);
    return 0;
}

int del_link_by_index(link_t *head, int index) {
    if(NULL == head) return -1;

    int i;
    i = index;
    while(--i) {
        head = head->next;
    }
    del_head_link(head);
    return 0;
}

int del_link_by_data(link_t *head, const int data) {
    //1. 备份要删除节点的地址
    //2. 头节点保存后一个元素地址
    //3. 释放要删除的节点空间
    link_t *node, *parent, *nnode;
    node = head->next;
    parent = head;
    while(NULL != node->next) {
        if(data == node->data) {
            nnode = node->next;
            parent->next = nnode;
            free(node);
            break;
        }
        parent = node;
        node = node -> next;
    }
    return 0;
}

/* 返回找到元素的节点地址 */
link_t * locate_link(link_t *head, const data_t *data) {
    while(NULL != head->next) {
        head = head->next;
        if(*data == head->data) return head;
    }
}

link_t * locate_link_pre(link_t *head, const data_t *data) {
    while(NULL != head->next) {
        if(*data == head->data) return head;
        head = head->next;
    }
    return NULL;
}

int change_index_link(link_t *head, int index, const data_t *data) {
    if(index < 0) return -2;
    if(NULL == head->next) return -1;

    while(index --) {
        head = head->next;
        if(NULL == head->next) return -1;
    }
    head->next->data = *data;
    return 0;
}

int get_index_link(link_t *head, int index, data_t *databuf) {
    if(index < 0) return -2;
    if(NULL == head->next) return -1;
    while(index --) {
        head = head->next;
        if(NULL == head->next) return -1;
    }
    *databuf = head->next->data;
    return 0;
}

int is_empty_link(link_t *head) {
    return NULL == head->next;
}

int clean_link(link_t *head) {
    while(!is_empty_link(head)) {
        del_head_link(head);
    }
    return 0;
}

int des_link(link_t **headp) {
   clean_link(*headp);
   free(*headp);
   *headp = NULL;
   return 0;
}

void print_link(link_t *head)
{
    link_t *p;
    p = head;
    while(NULL != p->next) {
        p = p->next;
        printf("%d ", p->data);
    }
    printf("\n");
}

int main(int argc, const char *argv[])
{
    data_t buf;
    link_t *p;
    p = create_link();

    buf = 250;
    printf("初始化链表完成：\n");
    for(buf = 8; buf >=0; buf--) {
        ins_head_link(p, &buf);
    }
    print_link(p);


    printf("按位置插入数据：3, 400\n");
    ins_index_link(p, 3, 400);
    print_link(p);


    printf("从链表头删除数据：\n");
    del_head_link(p);
    print_link(p);
    del_head_link(p);
    print_link(p);

    printf("删除指定数据的节点：\n");
    del_link_by_data(p, 5);
    print_link(p);

    printf("删除指定位置的节点：\n");
    del_link_by_index(p, 4);
    print_link(p);

    printf("查找链表中的数据6：\n");
    link_t *temp;
    data_t fdata;
    fdata = 6;
    temp = locate_link_pre(p, &fdata);
    if(NULL != temp) printf("locate: %d\n", temp->data);
    print_link(p);

}
